package 动态规划;


public class Solution494 {

    public static void main(String[] args) {


        int[] nums = new int[]{1, 1, 1, 1, 1};
        System.out.println(findTargetSumWays(nums, 3));

    }

    public static int findTargetSumWays(int[] nums, int target) {

        return process(nums, target, 0, 0);
    }

    //含义：从index位置上，到达target目标和方法数
    //index范围：[0～num.length]
    //rest:[0~target]代表当前值
    public static int process(int[] nums, int target, int index, int rest) {
        //只有当全部数字用上，并且最后值等于目标值才可以算
        if (index == nums.length) {
            if (rest == target) {
                return 1;
            } else {
                return 0;
            }
        }
        Thread thread=new Thread();
        thread.interrupt();
        //+本位置
        int p1 = process(nums, target, index + 1, rest + nums[index]);
        //-本位置
        int p2 = process(nums, target, index + 1, rest - nums[index]);
        return p1 + p2;
    }

//    public static int dp(int[] nums, int target){
//
//
//    }


}
